package main.Q1801_1900;

import java.util.HashSet;
import java.util.Set;

public class Q1891_1900 {
    public static void main(String[] args) {
        System.out.println("Question1891：");
        System.out.println("Question1892：");
        System.out.println("Question1893：");
        System.out.println("Question1894：找到需要补充粉笔的学生编号");
        System.out.println("Question1895：");
        System.out.println("Question1896：");
        System.out.println("Question1897：");
        System.out.println("Question1898：可移动字符的最大数目");
        System.out.println("Question1899：");
        System.out.println("Question1900：");
    }
}

class Question1894{
    public int chalkReplacer(int[] chalk, int k) {
        int length=chalk.length,index=-1;
        int[] dp=new int[length];//前缀和
        for (int i=0;i<length;i++){
            if (k<chalk[i]) {//未完成一轮
                index=i;
                break;
            }
            if (i==0) dp[i]=chalk[i];//填充前缀和数组
            else dp[i]=dp[i-1]+chalk[i];
            k-=chalk[i];//消耗
        }
        if (index==-1){//一轮未完成
            k=k%dp[length-1];//省略多轮过程
            int left=0,right=length-1;
            if (k<dp[0]) index=0;
            else {
                while (true) {
                    int mid = left + (right - left) / 2;
                    if ((dp[mid] == k) || (dp[mid] < k && dp[mid + 1] > k)) {//正好消耗完或下一个消耗不足
                        index = mid + 1;
                        break;
                    } else if (dp[mid] > k && dp[mid - 1] < k) {//当前消耗不足
                        index = mid;
                        break;
                    } else if (dp[mid] > k && dp[mid - 1] > k) right = mid - 1;
                    else if (dp[mid] < k && dp[mid + 1] < k) left = mid + 1;
                }
            }
        }
        return index;
    }
}

class Question1898{
    public boolean process2(String s,char[] ptr){
        char[] str=s.toCharArray();
        int i=0,j=0;
        if (ptr.length>s.length()) return false;
        while (i<str.length&&j< ptr.length){
            if (str[i]==ptr[j]) j++;
            i++;
        }
        if (j< ptr.length) return false;
        else return true;
    }
    public String process1(char[] str,int[] removable,int mid){
        StringBuffer result=new StringBuffer();
        Set<Integer> set=new HashSet<>();
        for (int i=0;i<=mid;i++) set.add(removable[i]);
        for (int i=0;i< str.length;i++){
            if (!set.contains(i)) result.append(str[i]);
        }
        return result.toString();
    }
    public int maximumRemovals(String s, String p, int[] removable) {
        int left=0,right=removable.length;
        char[] str=s.toCharArray(),ptr=p.toCharArray();
        String temp=null;
        while (left<right){
            int mid=left+(right-left)/2;
            temp=process1(str,removable,mid);
            if (process2(temp,ptr)) left=mid+1;
            else right=mid;
        }
        return left;
    }
}